home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / gnu / gnulib / dkbtrace / pbmplus / source / libtiff / tif_fax3.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-08-23  |  29.5 KB  |  1,152 lines
  1. #ifndef lint
  2. static char rcsid[] = "$Header: /usr/people/sam/tiff/libtiff/RCS/tif_fax3.c,v 1.51 91/08/22 18:17:45 sam Exp $";
  3. #endif
  4.  
  5. /*
  6.  * Copyright (c) 1990, 1991 Sam Leffler
  7.  * Copyright (c) 1991 Silicon Graphics, Inc.
  8.  *
  9.  * Permission to use, copy, modify, distribute, and sell this software and 
  10.  * its documentation for any purpose is hereby granted without fee, provided
  11.  * that (i) the above copyright notices and this permission notice appear in
  12.  * all copies of the software and related documentation, and (ii) the names of
  13.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  14.  * publicity relating to the software without the specific, prior written
  15.  * permission of Sam Leffler and Silicon Graphics.
  16.  * 
  17.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  18.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  19.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  20.  * 
  21.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  22.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  23.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  24.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  25.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  26.  * OF THIS SOFTWARE.
  27.  */
  28.  
  29. /*
  30.  * TIFF Library.
  31.  *
  32.  * CCITT Group 3 and Group 4 Compression Support.
  33.  */
  34. #include "tiffioP.h"
  35. #include <stdio.h>
  36. #include <assert.h>
  37. #include "tif_fax3.h"
  38. #define    G3CODES
  39. #include "t4.h"
  40. #include "g3states.h"
  41.  
  42. typedef struct {
  43.     Fax3BaseState b;
  44. } Fax3DecodeState;
  45.  
  46. typedef struct {
  47.     Fax3BaseState b;
  48.     u_char    *wruns;
  49.     u_char    *bruns;
  50.     short    k;            /* #rows left that can be 2d encoded */
  51.     short    maxk;            /* max #rows that can be 2d encoded */
  52. } Fax3EncodeState;
  53.  
  54. #if USE_PROTOTYPES
  55. static    Fax3PreDecode(TIFF *);
  56. static    Fax3Decode(TIFF*, u_char *, int, u_int);
  57. static    int Fax3Decode1DRow(TIFF*, u_char *, int);
  58. static    Fax3PreEncode(TIFF *);
  59. static    Fax3PostEncode(TIFF *);
  60. static    Fax3Encode(TIFF*, u_char *, int, u_int);
  61. static    int Fax3Encode1DRow(TIFF *, u_char *, int);
  62. static    Fax3Close(TIFF *);
  63. static    Fax3Cleanup(TIFF *);
  64. static    void *Fax3SetupState(TIFF *, int);
  65. static    void fillspan(char *, int, int);
  66. static    int findspan(u_char **, int, int, u_char *);
  67. static    int finddiff(u_char *, int, int);
  68. static    void skiptoeol(TIFF *, int);
  69. static    void putbits(TIFF *, u_int, u_int);
  70. static    void putcode(TIFF *, tableentry *);
  71. static    void putspan(TIFF *, int, tableentry *);
  72. extern    int TIFFFlushData1(TIFF *);
  73. #else
  74. static    int Fax3PreEncode(), Fax3Encode(), Fax3PostEncode();
  75. static    int Fax3Encode1DRow();
  76. static    int Fax3Decode(), Fax3PreDecode();
  77. static    int Fax3Decode1DRow();
  78. static    int Fax3Close(), Fax3Cleanup();
  79. static    void *Fax3SetupState();
  80. static    void fillspan();
  81. static    int findspan();
  82. static    int finddiff();
  83. static    void skiptoeol();
  84. static    void putbits();
  85. static    void putcode();
  86. static    void putspan();
  87. extern    int TIFFFlushData1();
  88. #endif
  89.  
  90. TIFFInitCCITTFax3(tif)
  91.     TIFF *tif;
  92. {
  93.     tif->tif_predecode = Fax3PreDecode;
  94.     tif->tif_decoderow = Fax3Decode;
  95.     tif->tif_decodestrip = Fax3Decode;
  96.     tif->tif_decodetile = Fax3Decode;
  97.     tif->tif_preencode = Fax3PreEncode;
  98.     tif->tif_postencode = Fax3PostEncode;
  99.     tif->tif_encoderow = Fax3Encode;
  100.     tif->tif_encodestrip = Fax3Encode;
  101.     tif->tif_encodetile = Fax3Encode;
  102.     tif->tif_close = Fax3Close;
  103.     tif->tif_cleanup = Fax3Cleanup;
  104.     tif->tif_options |= FAX3_CLASSF;    /* default */
  105.     tif->tif_flags |= TIFF_NOBITREV;    /* we handle bit reversal */
  106.     return (1);
  107. }
  108.  
  109. TIFFModeCCITTFax3(tif, isClassF)
  110.     TIFF *tif;
  111.     int isClassF;
  112. {
  113.     if (isClassF)
  114.         tif->tif_options |= FAX3_CLASSF;
  115.     else
  116.         tif->tif_options &= ~FAX3_CLASSF;
  117. }
  118.  
  119. static u_char bitMask[8] =
  120.     { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
  121. #define    isBitSet(sp)    ((sp)->b.data & bitMask[(sp)->b.bit])
  122.  
  123. #define    is2DEncoding(tif) \
  124.     (tif->tif_dir.td_group3options & GROUP3OPT_2DENCODING)
  125. #define    fetchByte(tif, sp) \
  126.     ((tif)->tif_rawcc--, (sp)->b.bitmap[*(u_char *)(tif)->tif_rawcp++])
  127.  
  128. #define    BITCASE(b)            \
  129.     case b:                \
  130.     code <<= 1;            \
  131.     if (data & (1<<(7-b))) code |= 1;\
  132.     len++;                \
  133.     if (code > 0) { bit = b+1; break; }
  134.  
  135. /*
  136.  * Skip over input until an EOL code is found.  The
  137.  * value of len is passed as 0 except during error
  138.  * recovery when decoding 2D data.  Note also that
  139.  * we don't use the optimized state tables to locate
  140.  * an EOL because we can't assume much of anything
  141.  * about our state (e.g. bit position).
  142.  */
  143. static void
  144. skiptoeol(tif, len)
  145.     TIFF *tif;
  146.     int len;
  147. {
  148.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  149.     register int bit = sp->b.bit;
  150.     register int data = sp->b.data;
  151.     int code = 0;
  152.  
  153.     /*
  154.      * Our handling of ``bit'' is painful because
  155.      * the rest of the code does not maintain it as
  156.      * exactly the bit offset in the current data
  157.      * byte (bit == 0 means refill the data byte).
  158.      * Thus we have to be careful on entry and
  159.      * exit to insure that we maintain a value that's
  160.      * understandable elsewhere in the decoding logic.
  161.      */
  162.     if (bit == 0)            /* force refill */
  163.         bit = 8;
  164.     for (;;) {
  165.         switch (bit) {
  166.     again:    BITCASE(0);
  167.         BITCASE(1);
  168.         BITCASE(2);
  169.         BITCASE(3);
  170.         BITCASE(4);
  171.         BITCASE(5);
  172.         BITCASE(6);
  173.         BITCASE(7);
  174.         default:
  175.             if (tif->tif_rawcc <= 0)
  176.                 return;
  177.             data = fetchByte(tif, sp);
  178.             goto again;
  179.         }
  180.         if (len >= 12 && code == EOL)
  181.             break;
  182.         code = len = 0;
  183.     }
  184.     sp->b.bit = bit > 7 ? 0 : bit;    /* force refill */
  185.     sp->b.data = data;
  186. }
  187.  
  188. /*
  189.  * Return the next bit in the input stream.  This is
  190.  * used to extract 2D tag values and the color tag
  191.  * at the end of a terminating uncompressed data code.
  192.  */
  193. static int
  194. nextbit(tif)
  195.     TIFF *tif;
  196. {
  197.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  198.     int bit;
  199.  
  200.     if (sp->b.bit == 0 && tif->tif_rawcc > 0)
  201.         sp->b.data = fetchByte(tif, sp);
  202.     bit = isBitSet(sp);
  203.     if (++(sp->b.bit) > 7)
  204.         sp->b.bit = 0;
  205.     return (bit);
  206. }
  207.  
  208. static void
  209. invert(cp, n)
  210.     register unsigned char *cp;
  211.     register int n;
  212. {
  213.     while (n-- > 0) {
  214.         *cp = ~*cp;
  215.         cp++;
  216.     }
  217. }
  218.  
  219. /*
  220.  * Setup G3-related compression/decompression
  221.  * state before data is processed.  This routine
  222.  * is called once per image -- it sets up different
  223.  * state based on whether or not 2D encoding is used.
  224.  */
  225. static void *
  226. Fax3SetupState(tif, space)
  227.     TIFF *tif;
  228.     int space;
  229. {
  230.     TIFFDirectory *td = &tif->tif_dir;
  231.     Fax3BaseState *sp;
  232.     int cc = space;
  233.  
  234.     if (td->td_bitspersample != 1) {
  235.         TIFFError(tif->tif_name,
  236.             "Bits/sample must be 1 for Group 3/4 encoding/decoding");
  237.         return (0);
  238.     }
  239.     if (is2DEncoding(tif) || td->td_compression == COMPRESSION_CCITTFAX4)
  240.         cc += tif->tif_scanlinesize;
  241.     tif->tif_data = malloc(cc);
  242.     if (tif->tif_data == NULL) {
  243.         TIFFError(tif->tif_name, "No space for Fax3 state block");
  244.         return (0);
  245.     }
  246.     sp = (Fax3BaseState *)tif->tif_data;
  247.     sp->bitmap = (tif->tif_fillorder != td->td_fillorder ? 
  248.         TIFFBitRevTable : TIFFNoBitRevTable);
  249.     sp->white = (td->td_photometric == PHOTOMETRIC_MINISBLACK);
  250.     if (is2DEncoding(tif) || td->td_compression == COMPRESSION_CCITTFAX4) {
  251.         /*
  252.          * 2d encoding/decoding requires a scanline
  253.          * buffer for the ``reference line''; the
  254.          * scanline against which delta encoding
  255.          * is referenced.  The reference line must
  256.          * be initialized to be ``white.''
  257.          */
  258.         sp->refline = (u_char *)tif->tif_data + space;
  259.         bzero(sp->refline, tif->tif_scanlinesize);
  260.         if (sp->white == 1)
  261.             invert(sp->refline, tif->tif_scanlinesize);
  262.     } else
  263.         sp->refline = 0;
  264.     /*
  265.      * Calculate the scanline/tile widths.
  266.      */
  267.     if (isTiled(tif)) {
  268.         sp->rowbytes = TIFFTileRowSize(tif);
  269.         sp->rowpixels = tif->tif_dir.td_tilewidth;
  270.     } else {
  271.         sp->rowbytes = TIFFScanlineSize(tif);
  272.         sp->rowpixels = tif->tif_dir.td_imagewidth;
  273.     }
  274.     return (sp);
  275. }
  276.  
  277. /*
  278.  * Setup state for decoding a strip.
  279.  */
  280. static
  281. Fax3PreDecode(tif)
  282.     TIFF *tif;
  283. {
  284.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  285.  
  286.     if (sp == NULL) {
  287.         sp = (Fax3DecodeState *)Fax3SetupState(tif, sizeof (*sp));
  288.         if (!sp)
  289.             return (0);
  290.     }
  291.     sp->b.bit = 0;            /* force initial read */
  292.     sp->b.data = 0;
  293.     sp->b.tag = G3_1D;
  294.     /*
  295.      * If image has EOL codes, they precede each line
  296.      * of data.  We skip over the first one here so that
  297.      * when we decode rows, we can use an EOL to signal
  298.      * that less than the expected number of pixels are
  299.      * present for the scanline.
  300.      */
  301.     if ((tif->tif_options & FAX3_NOEOL) == 0) {
  302.         skiptoeol(tif, 0);
  303.         if (is2DEncoding(tif))
  304.             /* tag should always be 1D! */
  305.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  306.     }
  307.     return (1);
  308. }
  309.  
  310. /*
  311.  * Fill a span with ones.
  312.  */
  313. static void
  314. fillspan(cp, x, count)
  315.     register char *cp;
  316.     register int x, count;
  317. {
  318.     static unsigned char masks[] =
  319.         { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
  320.  
  321.     if (count <= 0)
  322.         return;
  323.     cp += x>>3;
  324.     if (x &= 7) {            /* align to byte boundary */
  325.         if (count < 8 - x) {
  326.             *cp++ |= masks[count] >> x;
  327.             return;
  328.         }
  329.         *cp++ |= 0xff >> x;
  330.         count -= 8 - x;
  331.     }
  332.     while (count >= 8) {
  333.         *cp++ = 0xff;
  334.         count -= 8;
  335.     }
  336.     *cp |= masks[count];
  337. }
  338.  
  339. /*
  340.  * Decode the requested amount of data.
  341.  */
  342. static
  343. Fax3Decode(tif, buf, occ, s)
  344.     TIFF *tif;
  345.     u_char *buf;
  346.     int occ;
  347.     u_int s;
  348. {
  349.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  350.  
  351.     bzero(buf, occ);        /* decoding only sets non-zero bits */
  352.     while (occ > 0) {
  353.         if (sp->b.tag == G3_1D) {
  354.             if (!Fax3Decode1DRow(tif, buf, sp->b.rowpixels))
  355.                 return (0);
  356.         } else {
  357.             if (!Fax3Decode2DRow(tif, buf, sp->b.rowpixels))
  358.                 return (0);
  359.         }
  360.         if (is2DEncoding(tif)) {
  361.             /*
  362.              * Fetch the tag bit that indicates
  363.              * whether the next row is 1d or 2d
  364.              * encoded.  If 2d-encoded, then setup
  365.              * the reference line from the decoded
  366.              * scanline just completed.
  367.              */
  368.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  369.             if (sp->b.tag == G3_2D)
  370.                 bcopy(buf, sp->b.refline, sp->b.rowbytes);
  371.         }
  372.         buf += sp->b.rowbytes;
  373.         occ -= sp->b.rowbytes;
  374.     }
  375.     return (1);
  376. }
  377.  
  378. /*
  379.  * Decode a run of white.
  380.  */
  381. static int
  382. decode_white_run(tif)
  383.     TIFF *tif;
  384. {
  385.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  386.     short state = sp->b.bit;
  387.     short action;
  388.     int runlen = 0;
  389.  
  390.     for (;;) {
  391.         if (sp->b.bit == 0) {
  392.     nextbyte:
  393.             if (tif->tif_rawcc <= 0)
  394.                 return (G3CODE_EOF);
  395.             sp->b.data = fetchByte(tif, sp);
  396.         }
  397.         action = TIFFFax1DAction[state][sp->b.data];
  398.         state = TIFFFax1DNextState[state][sp->b.data];
  399.         if (action == ACT_INCOMP)
  400.             goto nextbyte;
  401.         if (action == ACT_INVALID)
  402.             return (G3CODE_INVALID);
  403.         if (action == ACT_EOL)
  404.             return (G3CODE_EOL);
  405.         sp->b.bit = state;
  406.         action = RUNLENGTH(action - ACT_WRUNT);
  407.         runlen += action;
  408.         if (action < 64)
  409.             return (runlen);
  410.     }
  411.     /*NOTREACHED*/
  412. }
  413.  
  414. /*
  415.  * Decode a run of black.
  416.  */
  417. static int
  418. decode_black_run(tif)
  419.     TIFF *tif;
  420. {
  421.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  422.     short state = sp->b.bit + 8;
  423.     short action;
  424.     int runlen = 0;
  425.  
  426.     for (;;) {
  427.         if (sp->b.bit == 0) {
  428.     nextbyte:
  429.             if (tif->tif_rawcc <= 0)
  430.                 return (G3CODE_EOF);
  431.             sp->b.data = fetchByte(tif, sp);
  432.         }
  433.         action = TIFFFax1DAction[state][sp->b.data];
  434.         state = TIFFFax1DNextState[state][sp->b.data];
  435.         if (action == ACT_INCOMP)
  436.             goto nextbyte;
  437.         if (action == ACT_INVALID)
  438.             return (G3CODE_INVALID);
  439.         if (action == ACT_EOL)
  440.             return (G3CODE_EOL);
  441.         sp->b.bit = state;
  442.         action = RUNLENGTH(action - ACT_BRUNT);
  443.         runlen += action;
  444.         if (action < 64)
  445.             return (runlen);
  446.         state += 8;
  447.     }
  448.     /*NOTREACHED*/
  449. }
  450.  
  451. /*
  452.  * Process one row of 1d Huffman-encoded data.
  453.  */
  454. static int
  455. Fax3Decode1DRow(tif, buf, npels)
  456.     TIFF *tif;
  457.     u_char *buf;
  458.     int npels;
  459. {
  460.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  461.     int x = 0;
  462.     int runlen;
  463.     short action;
  464.     short color = sp->b.white;
  465.     static char module[] = "Fax3Decode1D";
  466.  
  467.     for (;;) {
  468.         if (color == sp->b.white)
  469.             runlen = decode_white_run(tif);
  470.         else
  471.             runlen = decode_black_run(tif);
  472.         switch (runlen) {
  473.         case G3CODE_EOF:
  474.             TIFFError(module,
  475.                 "%s: Premature EOF at scanline %d (x %d)",
  476.                 tif->tif_name, tif->tif_row, x);
  477.             return (0);
  478.         case G3CODE_INVALID:    /* invalid code */
  479.             /*
  480.              * An invalid code was encountered.
  481.              * Flush the remainder of the line
  482.              * and allow the caller to decide whether
  483.              * or not to continue.  Note that this
  484.              * only works if we have a G3 image
  485.              * with EOL markers.
  486.              */
  487.             TIFFError(tif->tif_name,
  488.                "%s: Bad code word at scanline %d (x %d)",
  489.                module, tif->tif_row, x);
  490.             goto done;
  491.         case G3CODE_EOL:    /* premature end-of-line code */
  492.             TIFFWarning(tif->tif_name,
  493.                 "%s: Premature EOL at scanline %d (x %d)",
  494.                 module, tif->tif_row, x);
  495.             return (1);    /* try to resynchronize... */
  496.         }
  497.         if (x+runlen > npels)
  498.             runlen = npels-x;
  499.         if (runlen > 0) {
  500.             if (color)
  501.                 fillspan((char *)buf, x, runlen);
  502.             x += runlen;
  503.             if (x >= npels)
  504.                 break;
  505.         }
  506.         color = !color;
  507.     }
  508. done:
  509.     /*
  510.      * Cleanup at the end of the row.  This convoluted
  511.      * logic is merely so that we can reuse the code with
  512.      * two other related compression algorithms (2 & 32771).
  513.      *
  514.      * Note also that our handling of word alignment assumes
  515.      * that the buffer is at least word aligned.  This is
  516.      * the case for most all versions of malloc (typically
  517.      * the buffer is returned longword aligned).
  518.      */
  519.     if ((tif->tif_options & FAX3_NOEOL) == 0)
  520.         skiptoeol(tif, 0);
  521.     if (tif->tif_options & FAX3_BYTEALIGN)
  522.         sp->b.bit = 0;
  523.     if ((tif->tif_options & FAX3_WORDALIGN) && ((long)tif->tif_rawcp & 1))
  524.         (void) fetchByte(tif, sp);
  525.     return (x == npels);
  526. }
  527.  
  528. /*
  529.  * Group 3 2d Decoding support.
  530.  */
  531.  
  532. /*
  533.  * Return the next uncompressed mode code word.
  534.  */
  535. static int
  536. decode_uncomp_code(tif)
  537.     TIFF *tif;
  538. {
  539.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  540.     short code;
  541.  
  542.     do {
  543.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  544.             if (tif->tif_rawcc <= 0)
  545.                 return (UNCOMP_EOF);
  546.             sp->b.data = fetchByte(tif, sp);
  547.         }
  548.         code = TIFFFaxUncompAction[sp->b.bit][sp->b.data];
  549.         sp->b.bit = TIFFFaxUncompNextState[sp->b.bit][sp->b.data];
  550.     } while (code == ACT_INCOMP);
  551.     return (code);
  552. }
  553.  
  554. /*
  555.  * Process one row of 2d encoded data.
  556.  */
  557. int
  558. Fax3Decode2DRow(tif, buf, npels)
  559.     TIFF *tif;
  560.     u_char *buf;
  561.     int npels;
  562. {
  563. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  564.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  565.     int a0 = 0;
  566.     int b1 = 0;
  567.     int b2 = 0;
  568.     int run1, run2;        /* for horizontal mode */
  569.     short mode;
  570.     short color = sp->b.white;
  571.     static char module[] = "Fax3Decode2D";
  572.  
  573.     do {
  574.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  575.             if (tif->tif_rawcc <= 0) {
  576.                 TIFFError(module,
  577.                 "%s: Premature EOF at scanline %d",
  578.                     tif->tif_name, tif->tif_row);
  579.                 return (0);
  580.             }
  581.             sp->b.data = fetchByte(tif, sp);
  582.         }
  583.         mode = TIFFFax2DMode[sp->b.bit][sp->b.data];
  584.         sp->b.bit = TIFFFax2DNextState[sp->b.bit][sp->b.data];
  585.         switch (mode) {
  586.         case MODE_NULL:
  587.             break;
  588.         case MODE_PASS:
  589. #ifdef notdef
  590.             if (a0 || PIXEL(sp->b.refline, 0) == color) {
  591. #else
  592.             if (a0 || color || !PIXEL(sp->b.refline, 0)) {
  593. #endif
  594.                 b1 = finddiff(sp->b.refline, a0, npels);
  595.                 if (color == PIXEL(sp->b.refline, b1))
  596.                     b1 = finddiff(sp->b.refline, b1, npels);
  597.             } else
  598.                 b1 = 0;
  599.             b2 = finddiff(sp->b.refline, b1, npels);
  600.             if (color)
  601.                 fillspan((char *)buf, a0, b2 - a0);
  602.             a0 += b2 - a0;
  603.             break;
  604.         case MODE_HORIZ:
  605.             if (color == sp->b.white) {
  606.                 run1 = decode_white_run(tif);
  607.                 run2 = decode_black_run(tif);
  608.             } else {
  609.                 run1 = decode_black_run(tif);
  610.                 run2 = decode_white_run(tif);
  611.             }
  612.             /*
  613.              * Do the appropriate fill.  Note that we exit
  614.              * this logic with the same color that we enter
  615.              * with since we do 2 fills.  This explains the
  616.              * somewhat obscure logic below.
  617.              */
  618.             if (a0 + run1 > npels)
  619.                 run1 = npels - a0;
  620.             if (color)
  621.                 fillspan((char *)buf, a0, run1);
  622.             a0 += run1;
  623.             if (a0 + run2 > npels)
  624.                 run2 = npels - a0;
  625.             if (!color)
  626.                 fillspan((char *)buf, a0, run2);
  627.             a0 += run2;
  628.             break;
  629.         case MODE_VERT_V0:
  630.         case MODE_VERT_VR1:
  631.         case MODE_VERT_VR2:
  632.         case MODE_VERT_VR3:
  633.         case MODE_VERT_VL1:
  634.         case MODE_VERT_VL2:
  635.         case MODE_VERT_VL3:
  636.             if (a0 || color || !PIXEL(sp->b.refline, 0)) {
  637.                 b1 = finddiff(sp->b.refline, a0, npels);
  638.                 if (color == PIXEL(sp->b.refline, b1))
  639.                     b1 = finddiff(sp->b.refline, b1, npels);
  640.             } else
  641.                 b1 = 0;
  642.             b1 += mode - MODE_VERT_V0;
  643.             if (color)
  644.                 fillspan((char *)buf, a0, b1 - a0);
  645.             color = !color;
  646.             a0 += b1 - a0;
  647.             break;
  648.             case MODE_UNCOMP:
  649.             /*
  650.              * Uncompressed mode: select from the
  651.              * special set of code words.
  652.              */
  653.             do {
  654.                 mode = decode_uncomp_code(tif);
  655.                 switch (mode) {
  656.                 case UNCOMP_RUN1:
  657.                 case UNCOMP_RUN2:
  658.                 case UNCOMP_RUN3:
  659.                 case UNCOMP_RUN4:
  660.                 case UNCOMP_RUN5:
  661.                     run1 = mode - UNCOMP_RUN0;
  662.                     fillspan((char *)buf, a0+run1-1, 1);
  663.                     a0 += run1;
  664.                     break;
  665.                 case UNCOMP_RUN6:
  666.                     a0 += 5;
  667.                     break;
  668.                 case UNCOMP_TRUN0:
  669.                 case UNCOMP_TRUN1:
  670.                 case UNCOMP_TRUN2:
  671.                 case UNCOMP_TRUN3:
  672.                 case UNCOMP_TRUN4:
  673.                     run1 = mode - UNCOMP_TRUN0;
  674.                     a0 += run1;
  675.                     color = nextbit(tif) ?
  676.                         !sp->b.white : sp->b.white;
  677.                     break;
  678.                 case UNCOMP_INVALID:
  679.                     TIFFError(module,
  680.                 "%s: Bad uncompressed code word at scanline %d",
  681.                         tif->tif_name, tif->tif_row);
  682.                     goto bad;
  683.                 case UNCOMP_EOF:
  684.                     TIFFError(module,
  685.                         "%s: Premature EOF at scanline %d",
  686.                         tif->tif_name, tif->tif_row);
  687.                     return (0);
  688.                 }
  689.             } while (mode < UNCOMP_EXIT);
  690.             break;
  691.             case MODE_ERROR_1:
  692.             if ((tif->tif_options & FAX3_NOEOL) == 0) {
  693.                 TIFFWarning(tif->tif_name,
  694.                     "%s: Premature EOL at scanline %d (x %d)",
  695.                     module, tif->tif_row, a0);
  696.                 skiptoeol(tif, 7);    /* seen 7 0's already */
  697.                 return (1);        /* try to synchronize */
  698.             }
  699.             /* fall thru... */
  700.             case MODE_ERROR:
  701.             TIFFError(tif->tif_name,
  702.                 "%s: Bad 2D code word at scanline %d",
  703.                 module, tif->tif_row);
  704.             goto bad;
  705.             default:
  706.             TIFFError(tif->tif_name,
  707.                 "%s: Panic, bad decoding state at scanline %d",
  708.                 module, tif->tif_row);
  709.             return (0);
  710.         }
  711.     } while (a0 < npels);
  712. bad:
  713.     /*
  714.      * Cleanup at the end of row.  We check for
  715.      * EOL separately so that this code can be
  716.      * reused by the Group 4 decoding routine.
  717.      */
  718.     if ((tif->tif_options & FAX3_NOEOL) == 0)
  719.         skiptoeol(tif, 0);
  720.     return (a0 >= npels);
  721. #undef    PIXEL
  722. }
  723.  
  724. /*
  725.  * CCITT Group 3 FAX Encoding.
  726.  */
  727.  
  728. /*
  729.  * Write a variable-length bit-value to
  730.  * the output stream.  Values are
  731.  * assumed to be at most 16 bits.
  732.  */
  733. static void
  734. putbits(tif, bits, length)
  735.     TIFF *tif;
  736.     u_int bits, length;
  737. {
  738.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  739.     static int mask[9] =
  740.         { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
  741.  
  742.     while (length > sp->bit) {
  743.         sp->data |= bits >> (length - sp->bit);
  744.         length -= sp->bit;
  745.         Fax3FlushBits(tif, sp);
  746.     }
  747.     sp->data |= (bits & mask[length]) << (sp->bit - length);
  748.     sp->bit -= length;
  749.     if (sp->bit == 0)
  750.         Fax3FlushBits(tif, sp);
  751. }
  752.  
  753. /*
  754.  * Write a code to the output stream.
  755.  */
  756. static void
  757. putcode(tif, te)
  758.     TIFF *tif;
  759.     tableentry *te;
  760. {
  761.     putbits(tif, te->code, te->length);
  762. }
  763.  
  764. /*
  765.  * Write the sequence of codes that describes
  766.  * the specified span of zero's or one's.  The
  767.  * appropriate table that holds the make-up and
  768.  * terminating codes is supplied.
  769.  */
  770. static void
  771. putspan(tif, span, tab)
  772.     TIFF *tif;
  773.     int span;
  774.     tableentry *tab;
  775. {
  776.     while (span >= 2624) {
  777.         tableentry *te = &tab[63 + (2560>>6)];
  778.         putcode(tif, te);
  779.         span -= te->runlen;
  780.     }
  781.     if (span >= 64) {
  782.         tableentry *te = &tab[63 + (span>>6)];
  783.         assert(te->runlen == 64*(span>>6));
  784.         putcode(tif, te);
  785.         span -= te->runlen;
  786.     }
  787.     putcode(tif, &tab[span]);
  788. }
  789.  
  790. /*
  791.  * Write an EOL code to the output stream.  The zero-fill
  792.  * logic for byte-aligning encoded scanlines is handled
  793.  * here.  We also handle writing the tag bit for the next
  794.  * scanline when doing 2d encoding.
  795.  *
  796.  * Note that when doing 2d encoding, we byte-align
  797.  * the combination of the EOL+tag bits.  It is unclear
  798.  * (to me) from the documentation whether this is the
  799.  * correct behaviour, or whether the EOL should be
  800.  * aligned and the tag bit should be the first bit in
  801.  * the next byte.  I've implemented what seems to make
  802.  * the most sense.
  803.  */
  804. void
  805. Fax3PutEOL(tif)
  806.     TIFF *tif;
  807. {
  808.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  809.  
  810.     if (tif->tif_dir.td_group3options & GROUP3OPT_FILLBITS) {
  811.         /*
  812.          * Force bit alignment so EOL (+tag bit) will
  813.          * terminate on a byte boundary.  That is, force
  814.          * the bit alignment to 16-12 = 4 (or 16-13 = 3 for
  815.          * 2d encoding) before putting out the EOL code.
  816.          */
  817.         int align = 8 - (is2DEncoding(tif) ? 3 : 4);
  818.         if (align != sp->bit) {
  819.             if (align > sp->bit)
  820.                 align = sp->bit + (8 - align);
  821.             else
  822.                 align = sp->bit - align;
  823.             putbits(tif, 0, align);
  824.         }
  825.     }
  826.     putbits(tif, EOL, 12);
  827.     if (is2DEncoding(tif))
  828.         putbits(tif, sp->tag == G3_1D, 1);
  829. }
  830.  
  831. static u_char zeroruns[256] = {
  832.     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,    /* 0x00 - 0x0f */
  833.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0x10 - 0x1f */
  834.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x20 - 0x2f */
  835.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x30 - 0x3f */
  836.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x40 - 0x4f */
  837.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x50 - 0x5f */
  838.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x60 - 0x6f */
  839.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x70 - 0x7f */
  840.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x80 - 0x8f */
  841.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x90 - 0x9f */
  842.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xa0 - 0xaf */
  843.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xb0 - 0xbf */
  844.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xc0 - 0xcf */
  845.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xd0 - 0xdf */
  846.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xe0 - 0xef */
  847.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xf0 - 0xff */
  848. };
  849. static u_char oneruns[256] = {
  850.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x00 - 0x0f */
  851.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x10 - 0x1f */
  852.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x20 - 0x2f */
  853.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x30 - 0x3f */
  854.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x40 - 0x4f */
  855.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x50 - 0x5f */
  856.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x60 - 0x6f */
  857.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x70 - 0x7f */
  858.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x80 - 0x8f */
  859.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x90 - 0x9f */
  860.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xa0 - 0xaf */
  861.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xb0 - 0xbf */
  862.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xc0 - 0xcf */
  863.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xd0 - 0xdf */
  864.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0xe0 - 0xef */
  865.     4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 8,    /* 0xf0 - 0xff */
  866. };
  867.  
  868. /*
  869.  * Reset encoding state at the start of a strip.
  870.  */
  871. static
  872. Fax3PreEncode(tif)
  873.     TIFF *tif;
  874. {
  875.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  876.  
  877.     if (sp == NULL) {
  878.         sp = (Fax3EncodeState *)Fax3SetupState(tif, sizeof (*sp));
  879.         if (!sp)
  880.             return (0);
  881.         if (sp->b.white == 0) {
  882.             sp->wruns = zeroruns;
  883.             sp->bruns = oneruns;
  884.         } else {
  885.             sp->wruns = oneruns;
  886.             sp->bruns = zeroruns;
  887.         }
  888.     }
  889.     sp->b.bit = 8;
  890.     sp->b.data = 0;
  891.     sp->b.tag = G3_1D;
  892.     if (is2DEncoding(tif)) {
  893.         float res = tif->tif_dir.td_yresolution;
  894.         /*
  895.          * The CCITT spec says that when doing 2d encoding, you
  896.          * should only do it on K consecutive scanlines, where K
  897.          * depends on the resolution of the image being encoded
  898.          * (2 for <= 200 lpi, 4 for > 200 lpi).  Since the directory
  899.          * code initializes td_yresolution to 0, this code will
  900.          * select a K of 2 unless the YResolution tag is set
  901.          * appropriately.  (Note also that we fudge a little here
  902.          * and use 150 lpi to avoid problems with units conversion.)
  903.          */
  904.         if (tif->tif_dir.td_resolutionunit == RESUNIT_CENTIMETER)
  905.             res = (res * .3937) / 2.54;    /* convert to inches */
  906.         sp->maxk = (res > 150 ? 4 : 2);
  907.         sp->k = sp->maxk-1;
  908.     } else
  909.         sp->k = sp->maxk = 0;
  910.     return (1);
  911. }
  912.  
  913. /*
  914.  * 1d-encode a row of pixels.  The encoding is
  915.  * a sequence of all-white or all-black spans
  916.  * of pixels encoded with Huffman codes.
  917.  */
  918. static int
  919. Fax3Encode1DRow(tif, bp, bits)
  920.     TIFF *tif;
  921.     u_char *bp;
  922.     int bits;
  923. {
  924.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  925.     int bs = 0, span;
  926.  
  927.     for (;;) {
  928.         span = findspan(&bp, bs, bits, sp->wruns);    /* white span */
  929.         putspan(tif, span, TIFFFaxWhiteCodes);
  930.         bs += span;
  931.         if (bs >= bits)
  932.             break;
  933.         span = findspan(&bp, bs, bits, sp->bruns);    /* black span */
  934.         putspan(tif, span, TIFFFaxBlackCodes);
  935.         bs += span;
  936.         if (bs >= bits)
  937.             break;
  938.     }
  939.     return (1);
  940. }
  941.  
  942. static tableentry horizcode =
  943.     { 3, 0x1 };        /* 001 */
  944. static tableentry passcode =
  945.     { 4, 0x1 };        /* 0001 */
  946. static tableentry vcodes[7] = {
  947.     { 7, 0x03 },    /* 0000 011 */
  948.     { 6, 0x03 },    /* 0000 11 */
  949.     { 3, 0x03 },    /* 011 */
  950.     { 1, 0x1 },        /* 1 */
  951.     { 3, 0x2 },        /* 010 */
  952.     { 6, 0x02 },    /* 0000 10 */
  953.     { 7, 0x02 }        /* 0000 010 */
  954. };
  955.  
  956. /*
  957.  * 2d-encode a row of pixels.  Consult the CCITT
  958.  * documentation for the algorithm.
  959.  */
  960. int
  961. Fax3Encode2DRow(tif, bp, rp, bits)
  962.     TIFF *tif;
  963.     u_char *bp, *rp;
  964.     int bits;
  965. {
  966. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  967.     short white = ((Fax3BaseState *)tif->tif_data)->white;
  968.     int a0 = 0;
  969.     int a1 = (PIXEL(bp, 0) != white ? 0 : finddiff(bp, 0, bits));
  970.     int a2 = 0;
  971.     int b1 = (PIXEL(rp, 0) != white ? 0 : finddiff(rp, 0, bits));
  972.     int b2 = 0;
  973.  
  974.     for (;;) {
  975.         b2 = finddiff(rp, b1, bits);
  976.         if (b2 >= a1) {
  977.             int d = b1 - a1;
  978.             if (!(-3 <= d && d <= 3)) {    /* horizontal mode */
  979.                 a2 = finddiff(bp, a1, bits);
  980.                 putcode(tif, &horizcode);
  981.                 if (a0+a1 == 0 || PIXEL(bp, a0) == white) {
  982.                     putspan(tif, a1-a0, TIFFFaxWhiteCodes);
  983.                     putspan(tif, a2-a1, TIFFFaxBlackCodes);
  984.                 } else {
  985.                     putspan(tif, a1-a0, TIFFFaxBlackCodes);
  986.                     putspan(tif, a2-a1, TIFFFaxWhiteCodes);
  987.                 }
  988.                 a0 = a2;
  989.             } else {            /* vertical mode */
  990.                 putcode(tif, &vcodes[d+3]);
  991.                 a0 = a1;
  992.             }
  993.         } else {                /* pass mode */
  994.             putcode(tif, &passcode);
  995.             a0 = b2;
  996.         }
  997.         if (a0 >= bits)
  998.             break;
  999.         a1 = finddiff(bp, a0, bits);
  1000.         b1 = finddiff(rp, a0, bits);
  1001.         if (PIXEL(rp, b1) == PIXEL(bp, a0))
  1002.             b1 = finddiff(rp, b1, bits);
  1003.     }
  1004.     return (1);
  1005. #undef PIXEL
  1006. }
  1007.  
  1008. /*
  1009.  * Encode a buffer of pixels.
  1010.  */
  1011. static int
  1012. Fax3Encode(tif, bp, cc, s)
  1013.     TIFF *tif;
  1014.     u_char *bp;
  1015.     int cc;
  1016.     u_int s;
  1017. {
  1018.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  1019.  
  1020.     while (cc > 0) {
  1021.         Fax3PutEOL(tif);
  1022.         if (is2DEncoding(tif)) {
  1023.             if (sp->b.tag == G3_1D) {
  1024.                 if (!Fax3Encode1DRow(tif, bp, sp->b.rowpixels))
  1025.                     return (0);
  1026.                 sp->b.tag = G3_2D;
  1027.             } else {
  1028.                 if (!Fax3Encode2DRow(tif, bp, sp->b.refline, sp->b.rowpixels))
  1029.                     return (0);
  1030.                 sp->k--;
  1031.             }
  1032.             if (sp->k == 0) {
  1033.                 sp->b.tag = G3_1D;
  1034.                 sp->k = sp->maxk-1;
  1035.             } else
  1036.                 bcopy(bp, sp->b.refline, sp->b.rowbytes);
  1037.         } else {
  1038.             if (!Fax3Encode1DRow(tif, bp, sp->b.rowpixels))
  1039.                 return (0);
  1040.         }
  1041.         bp += sp->b.rowbytes;
  1042.         cc -= sp->b.rowbytes;
  1043.     }
  1044.     return (1);
  1045. }
  1046.  
  1047. static int
  1048. Fax3PostEncode(tif)
  1049.     TIFF *tif;
  1050. {
  1051.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  1052.  
  1053.     if (sp->bit != 8)
  1054.         Fax3FlushBits(tif, sp);
  1055.     return (1);
  1056. }
  1057.  
  1058. static
  1059. Fax3Close(tif)
  1060.     TIFF *tif;
  1061. {
  1062.     if ((tif->tif_options & FAX3_CLASSF) == 0) {    /* append RTC */
  1063.         int i;
  1064.         for (i = 0; i < 6; i++)
  1065.             Fax3PutEOL(tif);
  1066.         (void) Fax3PostEncode(tif);
  1067.     }
  1068. }
  1069.  
  1070. static
  1071. Fax3Cleanup(tif)
  1072.     TIFF *tif;
  1073. {
  1074.     if (tif->tif_data) {
  1075.         free(tif->tif_data);
  1076.         tif->tif_data = NULL;
  1077.     }
  1078. }
  1079.  
  1080. /*
  1081.  * Bit handling utilities.
  1082.  */
  1083.  
  1084. /*
  1085.  * Find a span of ones or zeros using the supplied
  1086.  * table.  The byte-aligned start of the bit string
  1087.  * is supplied along with the start+end bit indices.
  1088.  * The table gives the number of consecutive ones or
  1089.  * zeros starting from the msb and is indexed by byte
  1090.  * value.
  1091.  */
  1092. static int
  1093. findspan(bpp, bs, be, tab)
  1094.     u_char **bpp;
  1095.     int bs, be;
  1096.     register u_char *tab;
  1097. {
  1098.     register u_char *bp = *bpp;
  1099.     register int bits = be - bs;
  1100.     register int n, span;
  1101.  
  1102.     /*
  1103.      * Check partial byte on lhs.
  1104.      */
  1105.     if (bits > 0 && (n = (bs & 7))) {
  1106.         span = tab[(*bp << n) & 0xff];
  1107.         if (span > 8-n)        /* table value too generous */
  1108.             span = 8-n;
  1109.         if (n+span < 8)        /* doesn't extend to edge of byte */
  1110.             goto done;
  1111.         bits -= span;
  1112.         bp++;
  1113.     } else
  1114.         span = 0;
  1115.     /*
  1116.      * Scan full bytes for all 1's or all 0's.
  1117.      */
  1118.     while (bits >= 8) {
  1119.         n = tab[*bp];
  1120.         span += n;
  1121.         bits -= n;
  1122.         if (n < 8)        /* end of run */
  1123.             goto done;
  1124.         bp++;
  1125.     }
  1126.     /*
  1127.      * Check partial byte on rhs.
  1128.      */
  1129.     if (bits > 0) {
  1130.         n = tab[*bp];
  1131.         span += (n > bits ? bits : n);
  1132.     }
  1133. done:
  1134.     *bpp = bp;
  1135.     return (span);
  1136. }
  1137.  
  1138. /*
  1139.  * Return the offset of the next bit in the range
  1140.  * [bs..be] that is different from bs.  The end,
  1141.  * be, is returned if no such bit exists.
  1142.  */
  1143. static int
  1144. finddiff(cp, bs, be)
  1145.     u_char *cp;
  1146.     int bs, be;
  1147. {
  1148.     cp += bs >> 3;            /* adjust byte offset */
  1149.     return (bs + findspan(&cp, bs, be,
  1150.         (*cp & (0x80 >> (bs&7))) ? oneruns : zeroruns));
  1151. }
  1152.